// 提交链接：https://leetcode.cn/problems/cherry-pickup-ii/
// lc1463. 摘樱桃 II
// 完成日期：2024/11/23
// c++ 记忆化回溯 矩阵 动态规划

class Solution {
public:
    int cherryPickup(std::vector<std::vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        vector<vector<vector<int>>> cache(
            n, vector<vector<int>>(m, vector<int>(m, -1))
        );

        auto dfs = [&](auto&& self, int i, int j, int k) -> int {
            if (i < 0 || i >= n || j < 0 || j >= m || k < 0 || k >= m)
                return 0;
            if (cache[i][j][k] != -1)
                return cache[i][j][k];

            int ans = 0;
            int val = j == k ? g[i][j] : g[i][j] + g[i][k];

            ans = std::max(ans, val + self(self, i + 1, j, k));
            ans = std::max(ans, val + self(self, i + 1, j + 1, k));
            ans = std::max(ans, val + self(self, i + 1, j - 1, k));
            ans = std::max(ans, val + self(self, i + 1, j, k + 1));
            ans = std::max(ans, val + self(self, i + 1, j, k - 1));
            ans = std::max(ans, val + self(self, i + 1, j + 1, k + 1));
            ans = std::max(ans, val + self(self, i + 1, j - 1, k - 1));
            ans = std::max(ans, val + self(self, i + 1, j + 1, k - 1));
            ans = std::max(ans, val + self(self, i + 1, j - 1, k + 1));

            cache[i][j][k] = ans;
            return ans;
        };
        return dfs(dfs, 0, 0, m - 1);
    }
};